Формулы

Элементарные матрицы

• Обратная к перестановке строк: \(P_{ij}^{-1} = P_{ij}\)
• Обратная к масштабированию строки: \(D_i(\alpha)^{-1} = D_i(1/\alpha)\)
• Обратная к прибавлению строки: \(E_{ij}(\alpha)^{-1} = E_{ij}(-\alpha)\)
• Определитель перестановки строк: \(\det(P_{ij}) = -1\)
• Определитель масштабирования строки: \(\det(D_i(\alpha)) = \alpha\)
• Определитель прибавления строки: \(\det(E_{ij}(\alpha)) = 1\)
• Разложение обратимой матрицы на элементарные: \(A = E_1 E_2 \cdots E_k\), поэтому \(A^{-1} = E_k^{-1} \cdots E_1^{-1}\)

LU-разложение

• LU-разложение: \(A = LU\) (\(L\) — нижняя треугольная с единицами на диагонали, unit lower triangular; \(U\) — верхняя треугольная)
• Условие существования: все ведущие главные миноры \(M_k \neq 0\)
• LU с частичным выбором главного элемента (partial pivoting): \(PA = LU\) (существует для любой обратимой \(A\))
• LU с полным выбором главного элемента (complete pivoting): \(PAQ = LU\) (существует для любой матрицы \(A\))
• Стоимость LU-факторизации: \(\frac{2}{3}n^3\) flops
• Стоимость прямой/обратной подстановки: \(2n^2\) flops на одно решение

Решение треугольных систем

• Прямая подстановка (forward substitution): \[x_i = \frac{1}{l_{ii}}\left(b_i - \sum_{j=1}^{i-1} l_{ij}x_j\right)\]
• Обратная подстановка (back substitution): \[x_i = \frac{1}{u_{ii}}\left(b_i - \sum_{j=i+1}^{n} u_{ij}x_j\right)\]

LDU и специальные разложения

• LDU-разложение: \(A = LDU_0\), где \(D = \text{diag}(u_{11}, \ldots, u_{nn})\), \(U_0 = D^{-1}U\)
• Симметричное LDU: \(A = LDL^T\) (когда \(A = A^T\))
• Разложение Холецкого (Cholesky): \(A = LL^T\) (когда \(A\) симметрична положительно определённая, \(L\) с положительной диагональю)
• Стоимость Холецкого: \(\frac{1}{3}n^3\) flops

Положительная определённость

• Критерий Сильвестра (Sylvester’s Criterion): симметричная \(A\) положительно определена тогда и только тогда, когда все ведущие главные миноры \(M_k > 0\)

Определитель при выборе главного элемента

• Эффект перестановки строк: \(\det(P_{ij}A) = -\det(A)\)
• Эффект перестановки столбцов: \(\det(AP_{ij}) = -\det(A)\)
• Из \(PAQ = LU\): \(\det(A) = \pm \prod_{i} u_{ii}\)

Обращение матрицы

• Обратная \(2\times 2\): \[\begin{bmatrix} a & b \\ c & d \end{bmatrix}^{-1} = \frac{1}{ad-bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\]
• Транспонирование и обращение: \((A^{-1})^T = (A^T)^{-1}\)

Скалярное произведение и нормы

• Скалярное произведение (dot product, inner product в \(\mathbb{R}^n\)): \(\mathbf{u} \cdot \mathbf{v} = \sum_{i=1}^n u_i v_i\)
• Длина вектора (норма): \(\|\mathbf{v}\| = \sqrt{v_1^2 + v_2^2 + \cdots + v_n^2}\)
• Единичный вектор: \(\hat{\mathbf{v}} = \frac{\mathbf{v}}{\|\mathbf{v}\|}\) (при \(\mathbf{v} \neq \mathbf{0}\))
• Условие ортогональности: \(\mathbf{u} \perp \mathbf{v}\) тогда и только тогда, когда \(\mathbf{u} \cdot \mathbf{v} = 0\)

Ортогональные проекции

• Проекция \(\mathbf{v}\) на \(\mathbf{u}\): \(\text{proj}_{\mathbf{u}}(\mathbf{v}) = \frac{\mathbf{v} \cdot \mathbf{u}}{\mathbf{u} \cdot \mathbf{u}}\mathbf{u}\)
• Ортогональная составляющая: \(\mathbf{v} - \text{proj}_{\mathbf{u}}(\mathbf{v})\) ортогональна \(\mathbf{u}\)
• Свойство ортонормированного набора: \(\mathbf{e}_i \cdot \mathbf{e}_j = \delta_{ij} = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{if } i \neq j \end{cases}\)

Ортогонализация Грама — Шмидта (Gram–Schmidt)

• Общий шаг (\(j = 1, 2, \ldots, n\)): \[\mathbf{u}_j = \mathbf{v}_j - \sum_{i=1}^{j-1} \frac{\mathbf{v}_j \cdot \mathbf{u}_i}{\mathbf{u}_i \cdot \mathbf{u}_i}\mathbf{u}_i, \quad \mathbf{e}_j = \frac{\mathbf{u}_j}{\|\mathbf{u}_j\|}\]
• Первый вектор: \(\mathbf{u}_1 = \mathbf{v}_1\), \(\mathbf{e}_1 = \frac{\mathbf{u}_1}{\|\mathbf{u}_1\|}\)
• Второй вектор: \(\mathbf{u}_2 = \mathbf{v}_2 - \frac{\mathbf{v}_2 \cdot \mathbf{u}_1}{\mathbf{u}_1 \cdot \mathbf{u}_1}\mathbf{u}_1\), \(\mathbf{e}_2 = \frac{\mathbf{u}_2}{\|\mathbf{u}_2\|}\)

QR-разложение

• QR-факторизация: \(A = QR\), где \(Q^T Q = I\) (ортонормированные столбцы) и \(R\) — верхняя треугольная
• Вычисление \(R\): \(R = Q^T A\)
• Размерность \(Q\): матрица \(m \times n\) (\(m\) строк, \(n\) ортонормированных столбцов)
• Размерность \(R\): матрица \(n \times n\) верхняя треугольная с положительными диагональными элементами

Подпространства

• Столбцовое пространство (column space) (\(\text{Col}(A)\)): линейная оболочка столбцов \(A\); подпространство \(\mathbb{R}^m\) для \(A \in \mathbb{R}^{m \times n}\)
• Ядро / нуль-пространство (null space) (\(\text{Nul}(A)\)): \(\{\mathbf{x} \in \mathbb{R}^n \mid A\mathbf{x} = \mathbf{0}\}\); подпространство \(\mathbb{R}^n\)
• Полное решение: \(\mathbf{x} = \mathbf{x}_p + \mathbf{x}_n\), где \(\mathbf{x}_p\) — частное решение, а \(\mathbf{x}_n \in \text{Nul}(A)\)

Метод наименьших квадратов (least squares)

• Нормальные уравнения (normal equations): \(A^T A \hat{\mathbf{x}} = A^T \mathbf{b}\)
• Решение МНК (полный столбцовый ранг): \(\hat{\mathbf{x}} = (A^T A)^{-1} A^T \mathbf{b}\)
• Псевдообратная (pseudoinverse): \(A^+ = (A^T A)^{-1} A^T\)
• Система МНК через QR: \(R\hat{\mathbf{x}} = Q^T \mathbf{b}\) (решается обратной подстановкой)

Матрицы проекции

• Проекция на \(\mathcal{C}(A)\): \(\mathbf{p} = A(A^T A)^{-1} A^T \mathbf{b}\)
• Матрица проекции: \(P = A(A^T A)^{-1} A^T\) (проецирует на \(\mathcal{C}(A)\))
• Проекция на прямую (натянутую на \(\mathbf{a}\)): \(P = \dfrac{\mathbf{a}\mathbf{a}^T}{\mathbf{a}^T \mathbf{a}}\)
• Свойства матрицы проекции: \(P^2 = P\) (идемпотентность), \(P^T = P\) (симметричность)
• Дополняющая проекция: \(I - P\) проецирует на \(\mathcal{N}(A^T)\)

Собственные значения и собственные векторы

• Соотношение «собственное значение — собственный вектор»: \(A\mathbf{v} = \lambda\mathbf{v}\) (определяющее уравнение)
• Характеристическое уравнение: \(\det(A - \lambda I) = 0\) (корни — собственные значения)
• Поиск собственных векторов: \((A - \lambda I)\mathbf{v} = \mathbf{0}\) (однородная система для каждого \(\lambda\))
• След (trace): \(\text{tr}(A) = \lambda_1 + \lambda_2 + \cdots + \lambda_n\) (сумма собственных значений равна следу)
• Определитель: \(\det(A) = \lambda_1 \cdot \lambda_2 \cdots \lambda_n\) (произведение собственных значений)
• Диагонализация: \(A = PDP^{-1}\), где \(P = [\mathbf{v}_1 \ \mathbf{v}_2 \ \ldots \ \mathbf{v}_n]\) (столбцы — собственные векторы), \(D = \text{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)\)
• Степени через диагонализацию: \(A^k = PD^kP^{-1}\), где \(D^k = \text{diag}(\lambda_1^k, \lambda_2^k, \ldots, \lambda_n^k)\)
• Обратная через диагонализацию: \(A^{-1} = PD^{-1}P^{-1}\), где \(D^{-1} = \text{diag}(1/\lambda_1, 1/\lambda_2, \ldots, 1/\lambda_n)\) (если \(A\) обратима)
• Собственные значения треугольных матриц: для верхней или нижней треугольной \(A\) собственные значения — диагональные элементы
• Собственное значение степени матрицы: если \(\lambda\) — собственное значение \(A\), то \(\lambda^k\) — собственное значение \(A^k\)
• Собственное значение обратной: если \(\lambda\) — собственное значение обратимой \(A\), то \(1/\lambda\) — собственное значение \(A^{-1}\)
• Линейная независимость собственных векторов: векторы, отвечающие различным собственным значениям, линейно независимы
• Теорема Кэли — Гамильтона (Cayley–Hamilton): \(p(A) = 0\), где \(p(\lambda) = \det(A - \lambda I)\) — характеристический многочлен
• Спектральное отображение (spectral mapping): если у \(A\) собственные значения \(\lambda_1, \ldots, \lambda_n\) и \(p(x)\) — многочлен, то у \(p(A)\) собственные значения \(p(\lambda_1), \ldots, p(\lambda_n)\)
• Собственные значения симметричных матриц: если \(A = A^T\) (вещественная симметричная), все собственные значения вещественны
• Ортогональность собственных векторов: для вещественной симметричной \(A\) собственные векторы, отвечающие различным \(\lambda\), ортогональны
• Спектральное разложение (симметричный случай): \(A = Q\Lambda Q^T\), где \(Q\) ортогональна, \(\Lambda\) диагональна (на диагонали — \(\lambda\), столбцы \(Q\) — ортонормированные собственные векторы)

Подобные матрицы

• Определение подобия: \(B = P^{-1}AP\) для некоторой обратимой \(P\); \(B\) подобна \(A\)
• Степень подобной матрицы: если \(B = P^{-1}AP\), то \(B^k = P^{-1}A^kP\)
• Инварианты подобия: у подобных матриц совпадают определитель, след, характеристический многочлен и спектр
• Подобие и диагонализуемость: \(A\) диагонализуема тогда и только тогда, когда подобна диагональной \(D = \text{diag}(\lambda_1, \ldots, \lambda_n)\)
• Одновременная диагонализация: \(A\) и \(B\) одновременно диагонализуемы тогда и только тогда, когда \(AB = BA\) (коммутируют) и каждая отдельно диагонализуема

Комплексные числа

• Алгебраическая форма: \(z = a + bi\), где \(a = \text{Re}(z)\), \(b = \text{Im}(z)\), \(i^2 = -1\)
• Комплексно сопряжённое: \(\bar{z} = a - bi\); свойства: \(\overline{z+w} = \bar{z}+\bar{w}\), \(\overline{zw} = \bar{z}\bar{w}\), \(\overline{z/w} = \bar{z}/\bar{w}\)
• Модуль: \(|z| = \sqrt{a^2 + b^2} = \sqrt{z\bar{z}}\)
• Тригонометрическая / показательная форма: \(z = r(\cos\theta + i\sin\theta) = re^{i\theta}\), где \(r = |z|\), \(\theta = \arg(z)\)
• Формула Эйлера: \(e^{i\theta} = \cos\theta + i\sin\theta\)
• Произведение в полярной форме: \(z_1 z_2 = r_1 r_2 e^{i(\theta_1+\theta_2)}\) (модули перемножаются, аргументы складываются)
• Формула де Мойвра: \((re^{i\theta})^n = r^n e^{in\theta}\)

Комплексное скалярное произведение

• Эрмитово скалярное произведение в \(\mathbb{C}^n\): \(\langle\mathbf{x}, \mathbf{y}\rangle = \mathbf{x}^H\mathbf{y} = \sum_{i=1}^n \overline{x_i} y_i\)
• Норма в \(\mathbb{C}^n\): \(\|\mathbf{x}\| = \sqrt{\langle\mathbf{x},\mathbf{x}\rangle} = \sqrt{\sum_{i=1}^n |x_i|^2}\)
• Эрмитова симметрия: \(\langle\mathbf{x}, \mathbf{y}\rangle = \overline{\langle\mathbf{y}, \mathbf{x}\rangle}\)
• Положительная определённость: \(\langle\mathbf{x}, \mathbf{x}\rangle = \sum|x_i|^2 \geq 0\), равенство только при \(\mathbf{x} = \mathbf{0}\)
• Неравенство Коши — Буняковского — Шварца: \(|\langle\mathbf{x}, \mathbf{y}\rangle| \leq \|\mathbf{x}\|\|\mathbf{y}\|\)

Эрмитово сопряжённая матрица (conjugate transpose)

• Определение: \((A^H)_{ij} = \overline{A_{ji}}\); эквивалентно \(A^H = \overline{A}^T = \overline{A^T}\)
• Свойства: \((A^H)^H = A\), \((AB)^H = B^H A^H\), \((A+B)^H = A^H + B^H\), \((\alpha A)^H = \bar{\alpha} A^H\)
• Скалярное произведение через умножение: \(\langle\mathbf{x}, A\mathbf{y}\rangle = \langle A^H\mathbf{x}, \mathbf{y}\rangle\)

Эрмитовы и унитарные матрицы

• Эрмитова матрица: \(A = A^H\) (обобщение вещественной симметричной на \(\mathbb{C}\))
• Собственные значения эрмитовой матрицы: все вещественны
• Собственные векторы эрмитовой матрицы: для различных \(\lambda\) ортогональны (в смысле эрмитова скалярного произведения)
• Унитарная матрица: \(U^H U = I\) (эквивалентно \(U^{-1} = U^H\); обобщение вещественной ортогональной)
• Сохранение нормы и скалярного произведения: \(\|U\mathbf{x}\| = \|\mathbf{x}\|\) и \(\langle U\mathbf{x}, U\mathbf{y}\rangle = \langle\mathbf{x},\mathbf{y}\rangle\)
• Собственные значения унитарной матрицы: лежат на единичной окружности (\(|\lambda| = 1\))
• Определитель унитарной: \(|\det(U)| = 1\)
• Нормальная матрица (normal): \(AA^H = A^HA\) (эрмитовы и унитарные — частные случаи)
• Спектральная теорема (комплексный случай): любая эрмитова (и вообще нормальная) матрица унитарно диагонализуема: \(A = U\Lambda U^H\), где \(U\) унитарна, \(\Lambda\) диагональна с вещественными \(\lambda\) (для эрмитовой \(A\))
• Спектральное разложение: \(A = \sum_{i=1}^n \lambda_i \mathbf{u}_i \mathbf{u}_i^H\), где \(\mathbf{u}_i\) — ортонормированные собственные векторы
• Четыре фундаментальных подпространства (комплексный случай): \(\mathcal{C}(A^H)\), \(\mathcal{N}(A)\), \(\mathcal{C}(A)\), \(\mathcal{N}(A^H)\); везде используется \(A^H\) вместо \(A^T\)